home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1996 January: Mac OS SDK / Dev.CD Jan 96 SDK / Dev.CD Jan 96 SDK1.toast / Development Kits (Disc 1) / QuickDraw™ GX / Programming Stuff / Sample Code / Graphics Samples / Test Cubics (cubic to quad) ƒ / cubic library(Cubics2).c next >
Encoding:
C/C++ Source or Header  |  1995-04-10  |  10.9 KB  |  494 lines  |  [TEXT/MPS ]
  1. /*--------------------------------------------------------------------------------------------
  2.  
  3.     FILE:
  4.  
  5.         cubic library.c
  6.  
  7.     COPYRIGHT:
  8.     
  9.         ©1991, 1992 Apple Computer Inc.
  10.         All rights reserved
  11.  
  12. --------------------------------------------------------------------------------------------*/
  13.  
  14. #include "FixMath.h"
  15.  
  16. #include "graphics libraries.h"
  17.  
  18. /* this is the structyre for a single cubic -- from the library routines */
  19.  
  20. /*
  21.  
  22.             typedef struct    {                
  23.             
  24.                     gxPoint            a;
  25.                     gxPoint            b;
  26.                     gxPoint            c;
  27.                     gxPoint            d;
  28.                     
  29.             } cubic;
  30.  
  31. */
  32.  
  33. typedef struct    {                /* this structure contains the cached cubic coefficients */
  34.     
  35.         fixed            ax, ay;
  36.         fixed            bx, by;
  37.         fixed            cx, cy;
  38.         fixed            dx, dy;
  39.             
  40. } xcubic;
  41.  
  42. typedef struct    {                /* this structure is just for a gxPath */
  43.  
  44.         long        contours;
  45.         long        count;
  46.         long        flags;
  47.         gxPoint        data[ 32 ];
  48.  
  49. } SmallPath;
  50.  
  51. /* internal prototypes */
  52.  
  53. void CubicPath( SmallPath *pathptr, const cubic *cube, const long count );
  54.  
  55. long CountQuadratics( const cubic * );
  56. long xCountQuadratics( const cubic * );
  57.  
  58. gxPoint *ComputePoints( const cubic *cube, long    count,  gxPoint *storage );
  59.  
  60. /* now we define some macros to calculate the inner products */
  61.         
  62. #define xcube(xc,u) (FracMul(FracMul(FracMul((xc)->ax,(u))+(xc)->bx,(u))+(xc)->cx,(u))+(xc)->dx)
  63. #define    ycube(xc,u) (FracMul(FracMul(FracMul((xc)->ay,(u))+(xc)->by,(u))+(xc)->cy,(u))+(xc)->dy)
  64.  
  65. #define xcubeprime(xc,u) (FracMul(FracMul((3*(xc)->ax),(u))+(2*(xc)->bx),(u))+(xc)->cx)
  66. #define ycubeprime(xc,u) (FracMul(FracMul((3*(xc)->ay),(u))+(2*(xc)->by),(u))+(xc)->cy)
  67.  
  68. /*--------------------------------------------------------------------------------
  69.  
  70.     NewCubic
  71.     
  72.         this routine makes a new cubic that has a tolerance of one pixel.
  73.         
  74.             cubic            ->            a pointer to the cubic
  75.  
  76. --------------------------------------------------------------------------------*/
  77.  
  78. gxShape NewCubic( const cubic *cube )
  79. {    
  80.     SmallPath        pathrec;
  81.  
  82.     CubicPath( &pathrec, cube, xCountQuadratics( cube ) );
  83.     
  84.     /* now we are ready to create the gxPath */
  85.  
  86.     return( GXNewPaths((gxPaths *) &pathrec ) );
  87. }
  88.  
  89. /*--------------------------------------------------------------------------------
  90.  
  91.     NewCubic2
  92.     
  93.         this routine is the same as above except that it has an optional
  94.         parameter for determining how many points to include in a gxPath.  the number
  95.         determines the number of points 'off' the gxCurve which are needed.
  96.  
  97.             cubic            ->            a pointer to the cubic
  98.         
  99.         if you use this routine you should link it in with another which determines
  100.         the number of points to be used. here is an example that depends on a global
  101.         variable 'gerror' of type extended.  also, see the 'optimized' example for
  102.         'xCountQuadratics' futher below.
  103.         
  104.         extended gerror = 1.0;
  105.         
  106.         long CountQuadratics( const cubic *cube )
  107.             {
  108.                 long            count;
  109.                 extended    a, n;
  110.                 
  111.                 extended ax;
  112.                 extended ay;
  113.                 
  114.                 ax = Fix2X( - cube->a.x + 3 * cube->b.x - 3 * cube->c.x + cube->d.x );
  115.                 ay = Fix2X( - cube->a.y + 3 * cube->b.y - 3 * cube->c.y + cube->d.y );
  116.                 
  117.                 a = sqrt( ax * ax + ay * ay );
  118.                 
  119.                 n = power( ( a / ( 20.0 * gerror ) ), 1.0 / 3.0 );
  120.             
  121.                 count = ceil( n );
  122.             
  123.                 if( count <= 0 ) count += 1;
  124.             
  125.                 return( count );
  126.             }
  127.  
  128. --------------------------------------------------------------------------------*/
  129.  
  130. gxShape NewCubic2( const cubic *cube, const long count )
  131. {    
  132.     SmallPath        pathrec;
  133.  
  134.     CubicPath( &pathrec, cube, ( count <= 0 ) ? CountQuadratics( cube ) : count );
  135.  
  136.     /* now we are ready to create the gxPath */
  137.         
  138.     return( GXNewPaths((gxPaths *) &pathrec ) );
  139. }
  140. /*--------------------------------------------------------------------------------
  141.  
  142.     CubicPath
  143.     
  144.         this routine fills in a data structure for a gxPath with the information
  145.         of a cubic.
  146.         
  147.             pathptr        ->        a pointer to the gxPath
  148.             cube            ->        the cubic
  149.             count            ->        how many points to use
  150.         
  151. --------------------------------------------------------------------------------*/
  152.  
  153. void CubicPath( SmallPath *pathptr, const cubic *cube, const long count )
  154. {
  155.     long        *ptr;
  156.  
  157.     pathptr->contours = 1;
  158.     pathptr->count = count + 2;
  159.     pathptr->flags = 0x7FFFFFFF;
  160.     pathptr->flags &= ~( (unsigned long) 0x80000000 >> ( count + 1 ) );
  161.     
  162.     ptr = (fixed *) &pathptr->data[ 0 ];
  163.     
  164.     *ptr++ = cube->a.x;
  165.     *ptr++ = cube->a.y;
  166.  
  167.     (void) ComputePoints( cube, count,(gxPoint *) ptr );
  168. }
  169. /*--------------------------------------------------------------------------------
  170.  
  171.     DrawCubic
  172.     
  173.         this routine draws a cubic with the given fill
  174.         
  175.             cube            ->        the cubic
  176.             theFill        ->        how it should be filled
  177.         
  178. --------------------------------------------------------------------------------*/
  179. void DrawCubic( const cubic *cube, gxShapeFill theFill )
  180. {
  181.     gxShape    sh = NewCubic( cube );
  182.     
  183.     if( theFill ) GXSetShapeFill( sh, theFill );
  184.  
  185.     GXDrawShape( sh );
  186.     GXDisposeShape( sh );
  187. }
  188. /*--------------------------------------------------------------------------------
  189.  
  190.     SetCubic
  191.     
  192.         this routine sets the points inside of a gxPath to be those of the given
  193.         cubic
  194.         
  195.             dest        ->        the gxShape to set
  196.             cube        ->        the cubic
  197.         
  198. --------------------------------------------------------------------------------*/
  199.  
  200. void SetCubic( gxShape dest, const cubic *cube )
  201. {
  202.     SmallPath        pathrec;
  203.  
  204.     CubicPath( &pathrec, cube, xCountQuadratics( cube ) );
  205.     
  206.     GXSetPaths( dest, (gxPaths *) &pathrec );
  207. }
  208. /*--------------------------------------------------------------------------------
  209.  
  210.     ComputePoints
  211.     
  212.         this routine is where the cuadratic points get computed.  note that this
  213.         routine never fills in the last gxPoint in the code.
  214.         
  215.             cubic            ->            a pointer to the cubic
  216.             count            ->            the number of points other than the two end ones
  217.                                                 that we need to generate.
  218.             storage        ->            a place to put the points that are generated
  219.  
  220. --------------------------------------------------------------------------------*/
  221. gxPoint *ComputePoints( const cubic *cube, long    count,  gxPoint *storage )
  222. {
  223.     fixed        *ptr = storage;
  224.     
  225.     /* this routine assumes that the first gxPoint has been moved in by the caller */        
  226.         
  227.     if( 0 < count )
  228.         {
  229.             xcubic    x;
  230.             
  231.             fract        u;
  232.             fract        n;
  233.             
  234.             fixed            tempx1, tempy1;
  235.             fixed            tempx2, tempy2;
  236.  
  237.             fixed            ntempx1, ntempy1;
  238.             fixed            ntempx2, ntempy2;
  239.             
  240.             /* we now need to compute the coefficients for this cubic -- for efficient computation later  */
  241.             
  242.             x.ax = -cube->a.x + 3 * cube->b.x - 3 * cube->c.x + cube->d.x;
  243.             x.ay = -cube->a.y + 3 * cube->b.y - 3 * cube->c.y + cube->d.y;
  244.             x.bx = 3 * cube->a.x - 6 * cube->b.x + 3 * cube->c.x;
  245.             x.by = 3 * cube->a.y - 6 * cube->b.y + 3 * cube->c.y;
  246.             x.cx = -3 * cube->a.x + 3 * cube->b.x;
  247.             x.cy = -3 * cube->a.y + 3 * cube->b.y;
  248.             x.dx = cube->a.x;
  249.             x.dy = cube->a.y;
  250.             
  251.             n = FracDiv( 1, count );            /*        LONGINT / LONGINT -> frac        */
  252.             u = n;
  253.             
  254.             /* store the first pair of values */
  255.             
  256.             tempx1 = cube->a.x >> 1;
  257.             tempx2 = FracMul( x.cx, n ) >> 2;
  258.             
  259.             tempy1 = cube->a.y >> 1;
  260.             tempy2 = FracMul( x.cy, n ) >> 2;
  261.             
  262.             /* we start here  */
  263.             
  264.             for( ; 0 < count; --count )
  265.                 {
  266.                     /* compute the next gxPoint sequence */
  267.                     
  268.                     ntempx1 = xcube( &x, u ) >> 1;
  269.                     ntempx2 = FracMul( xcubeprime( &x, u ), n ) >> 2;
  270.  
  271.                     ntempy1 = ycube( &x, u ) >> 1;
  272.                     ntempy2 = FracMul( ycubeprime( &x, u ), n ) >> 2;
  273.                     
  274.                     /* now store the gxPoint */
  275.                     
  276.                     *ptr++ = tempx1 + tempx2 + ntempx1 - ntempx2;
  277.                     *ptr++ = tempy1 + tempy2 + ntempy1 - ntempy2;
  278.                     
  279.                     tempx1 = ntempx1;
  280.                     tempx2 = ntempx2;
  281.  
  282.                     tempy1 = ntempy1;
  283.                     tempy2 = ntempy2;
  284.                     
  285.                     u += n;
  286.                 }
  287.  
  288.             /* move in the last gxPoint of the cubic */
  289.  
  290.             *ptr++ = cube->d.x;
  291.             *ptr++ = cube->d.y;
  292.  
  293.         }
  294.     return((gxPoint *) ptr );
  295. }
  296.  
  297. /*--------------------------------------------------------------------------------
  298.  
  299.     xCountQuadratics
  300.     
  301.         this routine calculates the number of cubics that would be needed
  302.         to draw a with no more than a pixel error.
  303.         
  304.             cubic            ->            a pointer to the cubic
  305.  
  306. --------------------------------------------------------------------------------*/
  307.  
  308. long xCountQuadratics( const cubic *cube )
  309. {
  310.     fixed        ax, ay;
  311.     
  312.     short        temp;
  313.     long         count;
  314.     
  315.     /* first get the a vector components */
  316.     
  317.     ax = -cube->a.x + 3 * cube->b.x - 3 * cube->c.x + cube->d.x;
  318.     ay = -cube->a.y + 3 * cube->b.y - 3 * cube->c.y + cube->d.y;
  319.     
  320.     /* now make sure that they are positive */
  321.     
  322.     if( ax < 0 ) ax = -ax;
  323.     if( ay < 0 ) ay = -ay;
  324.     
  325.     /* now we need to pick the max one */
  326.     
  327.     ax = ( ay < ax ) ? ax : ay;
  328.     
  329.     /* we now divide by twenty and take the ceiling         */
  330.  
  331.     /*        NOTE: if you want the tolerance to be .5 then     */
  332.     /*        divide ax by 10, .25 -> 5, etc                                    */
  333.     
  334.     temp = ( FixDiv( ax, ff( 20 ) ) + 0xFFFF ) >> 16;
  335.         
  336.     /* this is a crude but fast and effective way of taking the cube root of        */
  337.     /* 'temp' which is between 0 and 27000                                                                            */
  338.     
  339.     if( temp <= 4096 )
  340.         {
  341.             if( temp <= 512 )
  342.                 {
  343.                     if( temp <= 64 )
  344.                         {
  345.                             if( temp <= 8 )
  346.                                 {
  347.                                     if( temp <= 1 )
  348.                                         count = 1;
  349.                                     else
  350.                                         count = 2;
  351.                                 }
  352.                             else
  353.                                 {
  354.                                     if( temp <= 27 )
  355.                                         count = 3;
  356.                                     else
  357.                                         count = 4;
  358.                                 }
  359.                         }
  360.                     else
  361.                         {
  362.                             if( temp <= 216 )
  363.                                 {
  364.                                     if( temp <= 125 )
  365.                                         count = 5;
  366.                                     else
  367.                                         count = 6;
  368.                                 }
  369.                             else
  370.                                 {
  371.                                     if( temp <= 343 )
  372.                                         count = 7;
  373.                                     else
  374.                                         count = 8;
  375.                                 }
  376.                         }
  377.                 }
  378.             else
  379.                 {
  380.                     if( temp <= 1728 )
  381.                         {
  382.                             if( temp <= 1000 )
  383.                                 {
  384.                                     if( temp <= 729 )
  385.                                         count = 9;
  386.                                     else
  387.                                         count = 10;
  388.                                 }
  389.                             else
  390.                                 {
  391.                                     if( temp <= 1331 )
  392.                                         count = 11;
  393.                                     else
  394.                                         count = 12;
  395.                                 }
  396.                         }
  397.                     else
  398.                         {
  399.                             if( temp <= 2744 )
  400.                                 {
  401.                                     if( temp <= 2197 )
  402.                                         count = 13;
  403.                                     else
  404.                                         count = 14;
  405.                                 }
  406.                             else
  407.                                 {
  408.                                     if( temp <= 3375 )
  409.                                         count = 15;
  410.                                     else
  411.                                         count = 16;
  412.                                 }
  413.                         }
  414.                 }
  415.         }
  416.     else
  417.         {
  418.             if( temp <= 13824 )
  419.                 {
  420.                     if( temp <= 8000 )
  421.                         {
  422.                             if( temp <= 5832 )
  423.                                 {
  424.                                     if( temp <= 4913 )
  425.                                         count = 17;
  426.                                     else
  427.                                         count = 18;
  428.                                 }
  429.                             else
  430.                                 {
  431.                                     if( temp <= 6859 )
  432.                                         count = 19;
  433.                                     else
  434.                                         count = 20;
  435.                                 }
  436.                         }
  437.                     else
  438.                         {
  439.                             if( temp <= 10648 )
  440.                                 {
  441.                                     if( temp <= 9261 )
  442.                                         count = 21;
  443.                                     else
  444.                                         count = 22;
  445.                                 }
  446.                             else
  447.                                 {
  448.                                     if( temp <= 12167 )
  449.                                         count = 23;
  450.                                     else
  451.                                         count = 24;
  452.                                 }
  453.                         }
  454.                 }
  455.             else
  456.                 {
  457.                     if( temp <= 21952 )
  458.                         {
  459.                             if( temp <= 17576 )
  460.                                 {
  461.                                     if( temp <= 15625 )
  462.                                         count = 25;
  463.                                     else
  464.                                         count = 26;
  465.                                 }
  466.                             else
  467.                                 {
  468.                                     if( temp <= 19683 )
  469.                                         count = 27;
  470.                                     else
  471.                                         count = 28;
  472.                                 }
  473.                         }
  474.                     else
  475.                         {
  476.                             if( temp <= 27000 )
  477.                                 {
  478.                                     if( temp <= 24389 )
  479.                                         count = 29;
  480.                                     else
  481.                                         count = 30;
  482.                                 }
  483.                             else
  484.                                 {
  485.                                     /* because our gxPath can only contain 32 -2 points we stop here */
  486.                                 
  487.                                     count = 30;
  488.                                 }
  489.                         }
  490.                 }
  491.         }
  492.         
  493.     return( count );
  494. }